import numpy as np

def construct_vandermonde_matrix(x_values):
    """
    构建给定 x 值的范德蒙德矩阵。

    参数:
    x_values -- x 值的数组

    返回:
    vandermonde_matrix -- 范德蒙德矩阵
    """
    # return np.vander(x_values, increasing=True)
    x_values = np.array(x_values)
    N = len(x_values)

    # 初始化一个空矩阵 v，大小为 (N, N)
    v = np.empty((N, N))
                 
    if N > 0:
        v[:, 0] = 1
    else:
       raise ValueError("Empty array to create vandermonde_matrix")
    
    if N > 1:
        # 将 x_values 扩展到 N-1 列以便广播
        v[:, 1:] = x_values[:, None]

        # 累积计算乘积得到幂值
        np.multiply.accumulate(v[:, 1:], axis=1, out=v[:, 1:])

    return v


def solve_vandermonde_system(vandermonde_matrix, y_values):
    """
    求解范德蒙德线性方程组以获得多项式系数。

    参数:
    vandermonde_matrix -- 范德蒙德矩阵
    y_values -- 插值点的 y 值的数组

    返回:
    coefficients -- 多项式系数的数组
    """
    coefficients = np.linalg.solve(vandermonde_matrix, y_values)

    return coefficients

def evaluate_polynomial(coefficients, x_experiment):
    """
    计算多项式在给定实验点的值。

    参数:
    coefficients -- 多项式系数的数组
    x_experiment -- 需要计算多项式值的 x 点数组

    返回:
    result -- 对应 x_experiment 的计算结果数组
    """
    result = []
    for x in x_experiment:
        y_value = 0
        for i, coeff in enumerate(coefficients):
            y_value += coeff * pow(x, i)
        result.append(y_value)
    return result

def vandermonde_interpolation(x_points, y_points, x_experiment):
    """
    根据范德蒙德插值计算在给定 x 值的插值结果。

    参数:
    x_points -- 用于插值的 x 值的数组
    y_points -- 用于插值的 y 值的数组
    x_experiment -- 需要计算插值结果的实验值数组

    返回:
    插值计算后的 y 值
    """
    V_matrix = construct_vandermonde_matrix(x_points)
    coefficients = solve_vandermonde_system(V_matrix, y_points)
    
    # 使用 np.polyval 计算结果，注意系数需要逆序
    result = evaluate_polynomial(coefficients, x_experiment)
    
    return result